package com.zhn;

import java.util.ArrayList;

/**
 * 给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
 *
 * 如果树中有不止一个众数，可以按 任意顺序 返回。
 *
 * 假定 BST 满足如下定义：
 *
 * 结点左子树中所含节点的值 小于等于 当前节点的值
 * 结点右子树中所含节点的值 大于等于 当前节点的值
 * 左子树和右子树都是二叉搜索树
 */
public class FindMode {
    ArrayList<Integer> arr;
    int maxCount;
    int count;
    TreeNode pre;
    public int[] findMode(TreeNode root) {
        arr = new ArrayList<>();
        maxCount = 0;
        count = 0;
        pre = null;
        travel(root);
        int[] res = new int[arr.size()];
        for(int i = 0; i < res.length; i++){
            res[i]=arr.get(i);
        }
        return res;
    }
    public void travel(TreeNode root){
        if(root == null){
            return;
        }
        travel(root.left);
        int rootValue = root.val;
        if(pre == null || rootValue != pre.val){
            count = 1;
        }else {
            count++;
        }
        if(count > maxCount){
            arr.clear();
            arr.add(rootValue);
            maxCount = count;
        }else if (count == maxCount){
            arr.add(rootValue);
        }
        pre = root;
        travel(root.right);
    }
}
